\begin{subanswer}{arraymissingnumber:a}
This is a little harder to figure out.
\index{tricks!start with simplest case}
If you struggle, think about the case with two missing numbers.
Then think of three.
This step-by-step thinking should help you to arrive at the general case.
For many brainteasers, it helps to start with the case of $n=1$ and then generalise, as discussed in appendix \ref{ap:tricks}.
The general solution to this question is similar to the case of one missing number.
You have $n-k$ numbers $x_1, x_2, x_3, \ldots , x_{n-k}$.
To find the $k$ missing values, calculate
\begin{align*}
& \sum_{i=1}^{n-k}{ x_i   } \\
& \sum_{i=1}^{n-k}{ x_i^2 } \\
& \sum_{i=1}^{n-k}{ x_i^3 } \\
& \quad\vdots \\
& \sum_{i=1}^{n-k}{ x_i^k }
\end{align*}
and compare these with their theoretical values.
The result is a system of $k$ equations to solve, with $k$ unknowns.
The answers represent the missing numbers.
For instance, assume you have three missing numbers, $m_1, m_2$, and $m_3$, which allows you to set up the following equations:
\begin{align*}
 \overbrace{\frac{n(n+1)}{2}}^{ \text{Theoretical} \atop \text{value} }
 &=
 \sum_{i=1}^{n-3}{ x_i }
+  m_1 + m_2 + m_3
\\
 \frac{n(n+1)(2n + 1)}{6}
 &=
 \sum_{i=1}^{n-3}{ x_i^2 }
+ m_1^2 + m_2^2 + m_3^2
\\
 \frac{n^2(n+1)^2}{4}
 &=
 \sum_{i=1}^{n-3}{ x_i^3 }
+ m_1^3 + m_2^3 + m_3^3
\text{.}
\end{align*}
You have three equations, and three unknowns.
You will probably have to solve this numerically, possibly by doing an exhaustive search over the integers from $1$ to $n$.
For the theoretical values, use Faulhaber's formula:
\[
  \sum_{k=1}^{n}{k^p} = \frac{1}{p+1} \sum_{j=0}^{p}{ (-1)^j \binom{p+1}{j} B_j n^{p+1-j} }
\]
where $B_j$ represents the Bernoulli numbers, or calculate them numerically.

An alternative way to answer this question was suggested by Jonathan Hon.
It involves initialising a boolean array of size $n$, with all the elements set to \verb+false+.
Then you loop over the array of integers and use each integer to set the value in the corresponding position (or position minus one for zero-indexed arrays) in the boolean array to \verb+true+.
Now you can loop over the boolean array and look for the values that are \verb+false+, revealing the missing numbers.

The difference between the two approaches is the complexity.
The first approach has space complexity of $O(k)$ since you only have to store the $k$ equations, but you also have to solve them.
The computational complexity of solving them is difficult to calculate, and it will depend on the algorithm you use.
Worst case scenario is the brute-force approach, where you try all the possible values,
which will have a worst-case complexity of $O(n!/((n-k)!k!))$, as we have to try all the combinations of $k$ integers.
The second approach has a space complexity of $O(n)$, since you have to store the boolean array, and a computational complexity of $O(n)$.
There is, however, more nuance to this method. If, instead of using a boolean array, you use an integer array and put the integers in their corresponding places, you will end up sorting the numbers.
The best sorting algorithms require $O(n \log(n))$ operations.
Have you cheated?
Kind of, but that is because you have more information than you would when sorting an arbitrary list of numbers; you know that the numbers are the integers from 1 to $n$, and you know there are only $k$ missing.
This is something that you may have to debate with the interviewer, but usually discussions like these are a sign that the interview is going well.
A question may have a \emph{best} or \emph{right} answer, but this isn't necessarily the answer the interviewer wants to hear.
Often you have to allow the interviewer to guide you to the answer they want.


\end{subanswer}

